#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int n;
    typedef long long ll;
    typedef pair<ll,ll> pii;
    const int INF=INT_MAX;
    vector<ll> pre;
    const int MAX=1e9+7;
    int dfs(vector<vector<pii>>& g,vector<ll>& d,int idx)
    {
        int ret=0;
        if(idx==n) return 1;
        if(pre[idx]!=-1) return pre[idx];
        for(auto& [x,d_x]:g[idx])
        {
            if(d[x]<d[idx])
            {
                ret+=dfs(g,d,x);
                ret%=MAX;
            }
        }
        pre[idx]=ret;
        return ret;
    }
    int countRestrictedPaths(int _n, vector<vector<int>>& edges) {
        n=_n;
        pre=vector<ll>(n+1,-1);
        vector<vector<pii>> g(n+1);
        for(auto& e:edges)
        {
            g[e[0]].emplace_back(e[1],e[2]);
            g[e[1]].emplace_back(e[0],e[2]);
        }
        vector<ll> d(n+1,INF);
        d[n]=0;
        priority_queue<pii,vector<pii>,greater<>> q;
        q.emplace(0,n);
        while(!q.empty())
        {
            auto [d_x,x]=q.top();
            q.pop();
            if(d_x>d[x]) continue;
            for(auto& [y,d_y]:g[x])
            {
                int new_d=d_y+d_x;
                if(new_d<d[y])
                {
                    d[y]=new_d;
                    q.emplace(d[y],y);
                }
            }
        }
        return dfs(g,d,1);
    }
};

int main()
{
    vector<vector<int>> vec={{1,2,1},{2,3,1},{3,4,1},{4,5,1}};
    Solution so;
    cout<<so.countRestrictedPaths(5,vec);
    return 0;
}